package com.example.algorithm.dynamicprogramming;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 给你一个 n x n 整数矩阵 arr ，请你返回 非零偏移下降路径 数字和的最小值。
 *  非零偏移下降路径 定义为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
 *
 *  示例 1：
 * 输入：arr = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：13
 * 解释：
 * 所有非零偏移下降路径包括：
 * [1,5,9], [1,5,7], [1,6,7], [1,6,8],
 * [2,4,8], [2,4,9], [2,6,7], [2,6,8],
 * [3,4,8], [3,4,9], [3,5,7], [3,5,9]
 * 下降路径中数字和最小的是[1,5,7] ，所以答案是13 。
 *
 *  示例 2：
 * 输入：grid = [[7]]
 * 输出：7
 */
public class Leetcode1289_MinFallingPathSumII {
    static class Solution {
        /**
         * 动态规划
         * 和 LeetCode64类似
         * 到达(i, j) 必须先到(i - 1, k) 其中 k != j and 0 < k < n
         * dp[i][j]表示从第一行跳到(i, j)的最小路径和
         * 则 dp[i][j] = min(dp[i - 1][k]) + grid[i][j] (其中 k != j)
         * @param grid
         * @return
         */
        public int minFallingPathSum(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int[][] dp = new int[m][n];  // dp[i][j]表示从第一行跳到(i, j)的最小路径和
            for (int j = 0; j < n; j++) dp[0][j] = grid[0][j];
            for (int i = 1; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    int[] tmp = Arrays.copyOf(dp[i - 1], n);
                    // 将上一行的状态值转化成List
                    List<Integer> tmpList = Arrays.stream(tmp).boxed().collect(Collectors.toList());
                    // 因为相邻数字不在原数组的同一列，所以要删去上一行同列的状态
                    tmpList.remove(j);
                    Queue<Integer> minHeap = new PriorityQueue<>(tmpList);
                    dp[i][j] = minHeap.peek() + grid[i][j];
                }
            }
            return Arrays.stream(dp[m - 1]).min().getAsInt();
        }
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        System.out.println(new Solution().minFallingPathSum(grid));
    }
}
